
#pragma once

#include "TypeDefin.h"
#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
输入：head = [1,2,3,4]
输出：[1,4,2,3]
 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//使用空间的简单明了
// 寻找中间节点 然后翻转后半部分
// 进行合并
//1 2 3 4 5 6   、1 6 2 5 3 4


//1 2 3 4 5     、如果是奇数的话 1 2  3 4 5    1 5 2 4 3


ListNode *reverse(ListNode *head) {

    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode *res = reverse(head->next);
    head->next->next = head;
    head->next = nullptr;

    return res;
}


void reorderList(ListNode *head) {

    //寻找链表中间

    ListNode *first = head;
    ListNode *second = head;


// 1 2 3 4 5 有问题
    while (second->next && first->next && second->next->next) {
        first = first->next;

        second = second->next->next;

    }

    //后端反转
    ListNode *needReverser = first->next;
    first->next = NULL;

    ListNode *res = reverse(needReverser);

    // 开始合并
    while (res && head) {
        ListNode *temp = head->next;//保留第二个节点
        ListNode *resSencond = res->next;
        head->next = res;
        res->next = temp;
        res = resSencond;
        head = temp;
    }


}
